package lc;

import java.util.Arrays;


import org.junit.Test;

public class Ex1575 {

    /**
输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
输出：4
解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
1 -> 3
1 -> 2 -> 3
1 -> 4 -> 3
1 -> 4 -> 2 -> 3
     */

     /**
      * 
      我们用f[i][j]代表从位置i出发，当前剩余的油量为j的前提下，到达目标位置finish的「路径数量」。
      */
    class Solution1 {
        int temp = (int)Math.pow(10, 9) + 7;
        int[][] f;
        int[] locations;
        int n, tar;
        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            this.locations = locations;
            this.n = locations.length;
            this.tar = finish;
            f = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(f[i], -1);
            }
            dfs(start, fuel);
            return f[start][fuel];
        }

        public int dfs(int i, int j) {
            // if (i == tar) {
            //     res = res % temp + 1;  //到达终点也还能走
            //     return 1;
            // }
            if (f[i][j] >= 0) {
                return f[i][j];
            }
            boolean flag = true;
            for (int k = 0; k < n; k++) {
                if (k != i) {
                    int t = Math.abs(locations[i] - locations[k]);
                    if (t <= j) {
                        flag = false;
                    }
                }
            }
            if (flag) {
                //无路可走
                f[i][j] = i != tar ? 0 : 1;
                return f[i][j];
            }
            int cur = i == tar ? 1 : 0;

            for (int k = 0; k < n; k++) {
                if (k != i) {
                    int t = Math.abs(locations[i] - locations[k]);
                    if (t <= j) {
                        cur += dfs(k, j - t);
                        cur %= temp;
                    }
                }
            }

            f[i][j] = cur;
            return cur;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{2,3,6,8,4};
        System.out.println(s.countRoutes(nums, 1, 3, 5));
    }

    class Solution {
        int temp = (int)Math.pow(10, 9) + 7;
        int[][] f;
        int[] locations;
        int n, tar;
        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            this.locations = locations;
            this.n = locations.length;
            this.tar = finish;
            f = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(f[i], -1);
                f[i][0] = 0;
            }
            f[finish][0] = 1; //位于终点，且没有油
            for (int j = 1; j <= fuel; j++) {
                for (int i = 0; i < n; i++) {
                    f[i][j] = i == finish ? 1 : 0;
                    if (Math.abs(locations[i] - locations[finish]) > j){
                        //直接都过不去，肯定过不去。
                        continue;
                    }
                    for (int k = 0; k < n; k++) {
                        if (i != k) {
                            int t = Math.abs(locations[i] - locations[k]);
                            if (t <= j) {
                                f[i][j] += f[k][j - t];
                                f[i][j] %= temp;
                            }
                        }
                    }

                }
            }
            return f[start][fuel];
        }

    }
}